МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
Національний університет “Львівська політехніка”
ІКНІТ
Методичні вказівки до лабораторної роботи № 7-8
"Транспортна задача. Метод потенціалів "
з дисципліни
“Математичні методи дослідження операцій”
для студентів бакалаврського напряму “Комп’ютерні науки”
Львів – 2011
Лабораторна робота № 7-8. Транспортна задача. Метод потенціалів
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми.
Короткі теоретичні відомості
Постановка транспортної задачі
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1( i ( m, 1 ( j ( n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Розв’язування транспортної задачі
1.2.1. Умови Т-задачі записуються у вигляді
ai
С =
bj b1 b2 b3 … bn
Введемо змінні хij ( 0, 1( i ( m, 1 ( j ( n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва ( ai ) в j пункт споживання ( bj ).
Необхідно знайти множину значень змінних хij ( 0, мінімізуючи функцію
L = ,
з виконанням умов
Матрицю
Х =
називають планом перевезень Т-задачі.
1.2.2.Визначення початкового опорного плану.
1.2.2.1. Метод «північно-західного кута» (ПЗК).
Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута. Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n.
Припустимо, що вже виконано t кроків.
Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай ( + ( = t + 2. Знаходимо x(( = min{}, де
.
Якщо , то заповнюється (-ий рядок матриці, починаючи з ((+1)-го елемента, нулями. Якщо , то заповнюється нулями (-й стовбець, починаючи з ((+1)-ї строки. При цьому
;
1.2.2.2. Приклад визначення початкового опорного плану методом «північно-західного кута» (ПЗК).
Записуються умову Т-задачі
ai
С =
bj 70 5 45 70
Перевіряємо умову балансу ; 190 = 190.
Будуємо початковий опорний план Х0:
Х0 =
x11 = min{60,70} = 60;
x21 = min{55,70-60} = 10;
x22 = min{5, 55-10} = 5;
x23 = min{45,55-10-5} = 40;
x33 = min(40, 45-40} = 5;
x34 = min{70,40-5} = 35;
x44 = 35.
Отриманий початковий опорний план Х0 невироджений ( m + n - 1 = 4+4-1 = 7).
Вартість перевезень в у.о. L0= = 60(1 + 10(3 + 5(4 + 40(1 + 5(8 + 35(3 + 35(1 = 330.
1.2.3.Метод потенціалів розв’язування транспортної задачі.
Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій.
1.2.3.1. Попередній етап.
1. Буду...
